# 什么是冒泡排序
# 冒泡排序 (Bubble Sort) 是经典的排序算法之一
# 基本思路 (从小到大排序为例, 冒泡结果是大数"冒"上来)
# 依次从头比较相邻的两个元素, 保留较大的元素, 再继续比较, 一轮结束, 就保留了最大的元素, 以此类推

# 实现思路(从小到大), 待排序的一组数应该是个list, 排序结果应该返回
# def bubble_sort(x):
#     return x

# 看循环次数, 第一轮比较找出最大元素, 第二轮找出第二大元素, ...
# [1, 2, 3], 三个元素只需比较两轮, 长度为 n, 只需要比较 n - 1 轮
# def bubble_sort(x):
#     # for i in range(len(x)-1):
#     for i in range(1, len(x)):
#         pass
#     return x

# 然后发现比较的过程也是循环, 这里就得使用嵌套循环, 外层控制轮次, 内层控制比较和是否换位
# def bubble_sort(x):
#     for i in range(1, len(x)):
#         for j in 比较次数:
#             如果 x[j] 比 x[j+1] 大, 则交换位置, 否则什么都不做, 继续下一次比较
#     return x

# 以 [1, 2, 3, 4, 5] 为例
# 第一轮要找出最大元素, 需要比较 长度 - 1 次
# 第二轮要找出第二大元素, 需要比较 长度 - 2 次
# 第i轮, 需要比较 长度 - i 次
def bubble_sort(x):
    for i in range(1, len(x)):
        for j in range(len(x) - i):
            if x[j] > x[j+1]:
                x[j], x[j+1] = x[j+1], x[j]
    return x

l = [5, 69, 12, 1, 66, 85, 21]
print("待排序的列表为: ", l)
print("从小到大排序后的结果为: ", bubble_sort(l))

'''
面试题
用python如何实现冒泡排序?[3]
- (如何是笔试题, 那么上面的代码就是答案, 如果需要口述, 逻辑如下)
- 冒泡的核心是两层嵌套循环来实现
    - 外层控制循环的轮次, 每一轮找出当前最符合的元素, 并冒泡
    - 内层控制每个元素两两比较的次数, 以及元素位置的交换
'''
